package main

import "fmt"

// 如何查找数组元素中的最大值和最小值

func main() {
	arr := []int{7, 3, 19, 40, 4, 7, 1}
	max, min := getMaxAndMin(arr)
	fmt.Println("max = ", max)
	fmt.Println("min = ", min)

	arr2 := []int{7, 3, 19, 40, 4, 7, 1}
	max, min = getMaxAndMinRe(arr2, 0, len(arr2)-1)
	fmt.Println("max = ", max)
	fmt.Println("min = ", min)
}

func getMaxAndMin(arr []int) (max, min int) {
	if arr == nil {
		return 0, 0
	}

	length := len(arr)
	min = arr[0]
	max = arr[0]

	for i := 0; i < length-1; i += 2 {
		if arr[i] > arr[i+1] {
			arr[i], arr[i+1] = arr[i+1], arr[i]
		}
	}

	for i := 2; i < length; i += 2 {
		if arr[i] < min {
			min = arr[i]
		}
	}

	for i := 3; i < length; i += 2 {
		if arr[i] > max {
			max = arr[i]
		}
	}

	if length%2 == 1 {
		if max < arr[length-1] {
			max = arr[length-1]
		}
		if min > arr[length-1] {
			min = arr[length-1]
		}
	}

	return
}

func getMaxAndMinRe(arr []int, start, end int) (max, min int) {
	if arr == nil {
		return 0, 0
	}

	m := (start + end) / 2

	if start == end {
		return arr[start], arr[start]
	}

	if start+1 == end {
		if arr[start] > arr[end] {
			return arr[start], arr[end]
		} else {
			return arr[end], arr[start]
		}
	}

	leftMax, leftMin := getMaxAndMinRe(arr, start, m)
	rightMax, rightMin := getMaxAndMinRe(arr, m+1, end)

	if leftMax > rightMax {
		max = leftMax
	} else {
		max = rightMax
	}

	if leftMin < rightMin {
		min = leftMin
	} else {
		min = rightMin
	}

	return
}
